import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] graph = {
                {1, 1, 0, 0},
                {1, 1, 1, 0},
                {0, 1, 1, 1},
                {0, 0, 1, 1}
        };
        System.out.println(s.minMalwareSpread(graph, new int[]{0, 1}));
    }

    public int minMalwareSpread(int[][] graph, int[] initial) {
        /**
         * 尽量减少恶意软件的传播Ⅱ*/
        // 1 预处理
        int n = graph.length;
        initialize(n, initial);

        // 2 将所有非病毒集合进行合并
        for(int i = 0; i < n; i++) {
            // -跳过病毒
            if(virus[i]) {
                continue;
            }
            for(int j = i + 1; j < n; j++) {
                // -跳过病毒
                if(virus[j]) {
                    continue;
                }
                if(graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        // 3 打标签（遍历每个病毒所关联的元素，对其元素所在集合打标签，仅对普通未感染元素打标签）
        for(int e: initial) {
            for(int k = 0; k < n; k++) {
                // -错误原因：打标签时没有排除k就是病毒的情况！
                // -判断条件：两者不相等 && 有关联关系 && 并且对方不为病毒
                if(e != k && graph[e][k] == 1 && !virus[k]) {
                    int tempVariable = find(k);
                    int tag = representative[tempVariable];
                    if(tag == -1 || tag == e) {
                        // -有效或病毒相等
                        representative[tempVariable] = e;
                    } else if(tag >= 0 || tag == -2) {
                        // -无效
                        representative[tempVariable] = -2;
                    }
                }
            }
        }

        // 4 统计（统计各个集合对应代表病毒所涉及的元素个数）
        int[] count = new int[n];
//        for(int i = 0; i < n; i++) {
//            if(representative[i] >= 0) {
//                // -此处确实需要注意，我们计数的是病毒感染个数，故需要以病毒为下标进行计数
//                count[representative[i]] += size[i];
//            }
//        }
        for(int i = 0; i < n; i++) {
            // -当前查看点必须是代表元素且有病毒
            if((i == find(i)) && representative[i]>=0) {
                // -此处确实需要注意，我们计数的是病毒感染个数，故需要以病毒为下标进行计数
                count[representative[i]] += size[i];
            }
        }

        // 5 返回值
        Arrays.sort(initial);
        int retIndex = initial[0];
        int maxCount = count[retIndex];
        for(int e: initial) {
            if(count[e] > maxCount) {
                retIndex = e;
                maxCount = count[e];
            }
        }
        return retIndex;
    }

    // 创建并查集
    public static int MAX_N;
    public static int[] father;
    public static int[] size;
    public static int[] stack;
    /**
     * 逻辑：
     *  virus:标记初始病毒
     *  representative:表示集合代表元素
     *      1，若是集合中不包含病毒，则为-1，表示空
     *      2，若是集合中存在多个病毒连接，则为-2，表示无效集合，即即使删去一个病毒，依旧无法拯救
     *      3，若是集合中存在一个病毒连接，则为病毒下标*/
    public static boolean[] virus;
    public static int[] representative;

    public static void initialize(int n, int[] initial) {
        /**
         * 并查集初始化*/
        MAX_N = n;
        father = new int[MAX_N];
        size = new int[MAX_N];
        stack = new int[MAX_N];
        virus = new boolean[MAX_N];
        representative = new int[MAX_N];
        // -标记病毒
        for(int e: initial) {
            virus[e] = true;
        }
        // -各结构赋值
        for(int i = 0; i < n; i++) {
            father[i] = i;
            size[i] = 1;
            representative[i] = -1;
        }

    }

    public static int find(int a) {
        /**
         * 找到a元素所在集合的代表元素-扁平化*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否处于同一集合中*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合-小挂大*/
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                // -小挂大
                size[fa] += size[fb];
                father[fb] = fa;
            } else {
                // -小挂大
                size[fb] += size[fa];
                father[fa] = fb;
            }
        }
    }
}
